package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *SplitArrayWithSameAverage_805_ 能否把一个数组 划分成两个数组(允许不连续) 两个数组平均值相同
 *describe:先把可能出现的长度找出来 用深搜超时 用动态规划搜索值区间 AC 47%
 *2018年10月27日 下午12:21:46
 */
public class SplitArrayWithSameAverage_805_ {
	public static void main(String[] args) {
		SplitArrayWithSameAverage_805_ test=new SplitArrayWithSameAverage_805_();
		//System.out.println(test.splitArraySameAverage(new int[] {1,2,3,4,5,6,7,8}));
		System.out.println(test.splitArraySameAverage1(new int[] {60,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30}));
	}
	
	
	/**
	 * describe:用动态规划 搜索值 
	 * 2018年10月27日 下午12:19:44
	 */
	public boolean splitArraySameAverage1(int[] A) {
	       int n = A.length;
	       int sum = 0;
	       for (int num : A)
	           sum += num;
	       for (int i = 1; i <= n/2; i++) {
	           if (i*sum%n == 0 && find(A, i, i*sum/n))
	               return true;
	       }
	       return false;
	   }
	   
	   private boolean find(int[] nums, int n, int target) {
	       boolean[][] dp = new boolean[target+1][n+1];
	       dp[0][0] = true;
	       for (int num : nums) {
	           for (int i = target; i >= num; i--) {
	               for (int j = n; j > 0; j--) {
	                   if (dp[i-num][j-1])
	                       dp[i][j] = true;
	               }
	           }
	       }
	       return dp[target][n];
	   }
	
	/**
	 * describe:划分之后深搜 超时
	 * 2018年10月27日 下午12:13:44
	 */
	public boolean splitArraySameAverage(int[] A) {
		int sum=0;
		for(int i:A)
			sum+=i;
		int spilt=1;//从2开始划分到A.length/2
		List<Integer> can=new ArrayList<Integer>();//可能成立的划分区间
		while(spilt<=A.length/2) {
			if(sum*spilt%A.length==0)
				can.add(spilt);
			++spilt;
		}
		for(int i:can) {
			int s= sum*i/A.length;
			if(help(A,i,s,0,0))
				return true;
		}
        return false;
    }
	
	private boolean help(int []A,int count,int sum,int index,int nowCount) {
		if(count==nowCount) {
			if(sum==0)
				return true;
			return false;
		}
		for(int i=index;i<=A.length+nowCount-count;++i) {
			if(sum-A[i]>=0) {
				if(help(A,count,sum-A[i],i+1,nowCount+1))
					return true;
			}
		}
		return false;
	}
}
